package effizienz;

public class Damen{
  public static int anz=0;

  public static void main(String[] args){
    int n=Integer.parseInt(args[0]);
    int[] hoch=new int[n];
    setze(hoch, 0);
    System.out.println("Das waren "+anz+" Möglichkeiten.");
  }

  public static void setze(int[] hoch, int d){
    for(int h=0; h<hoch.length; ++h){
      hoch[d]=h;
      if(gehtdas(hoch, d))
        if(d==hoch.length-1){// Gefunden! -> Ausgabe
          for(int i=0; i<hoch.length; ++i)
            System.out.print(1+hoch[i]+" ");
          System.out.println();
          anz++;
        } else setze(hoch, d+1);
    }
  }

  public static boolean gehtdas(int[] hoch, int d){
    for(int i=0; i<d; ++i){//Bedrohungen bei...
      if(hoch[i]==hoch[d])     return false;//  0 Grad
      if(hoch[i]+d-i==hoch[d]) return false;//+45 Grad
      if(hoch[i]-d+i==hoch[d]) return false;//-45 Grad
    }
    return true;
  }
}
